﻿using System;
using System.Collections.Generic;
using System.Text;
using Algoritmia.DataStructures.Maps;
using Algoritmia.Utils;

namespace Algoritmia.DataStructures.MergeFindSets
{
    public class MergeFindSet<T> : RankUnionMFSet<T>
    {
        public MergeFindSet(IEnumerable<IEnumerable<T>> sets = null, EqualityComparison<T> equalityComparison = null,
            Func<IEnumerable<T>, IMap<T, T>> createMap = null,
            Func<IEnumerable<T>, IMap<T, Lists.IList<T>>> createMapOfLists = null,
            Func<IEnumerable<T>, Lists.IList<T>> createList = null,
            Func<IEnumerable<T>, IMap<T, int>> createIntegerMap = null) 
            : base(sets,equalityComparison,createMap,createMapOfLists,createList,createIntegerMap)
        {
        }

        /// <summary>
        /// PathCompression implementation
        /// </summary>
        /// <param name="item"></param>
        /// <returns>Representant of the item family</returns>
        public override T Find(T item)
        {
            T r = item, aux = item;
            while (!_equalityComparison(r,_parent[r]))
            {
                r = _parent[r];
            }
            while (!_equalityComparison(aux,r))
            {
                _parent[aux] = r;
                aux = _parent[aux];
            }
            return r;
        }

        public override string ToString()
        {
            StringBuilder sb = new StringBuilder(String.Format("{0} <{1}> [", GetType().Name, typeof(T).Name));
            foreach (var family in this)
            {
                sb.Append(String.Format("[{0}]", string.Join(",", family)));
            }
            sb.Append(" ]");
            return sb.ToString();
        }
    }
}
